The use of synthetic images has become increasingly important and widespread in motion pictures and other commercial and scientific applications. A synthetic image typically represents a two-dimensional array of digital values, called picture elements or pixels, and thus is commonly regarded as a two-dimensional function.
Image synthesis is the process of creating synthetic images from scenes. As a general matter, digital images are generated by rasterization or, in the case of photorealistic images of three-dimensional scenes, by ray tracing. Both approaches aim at determining the appropriate color for each pixel by projecting the original function into the pixel basis. The discrete representation of the original function creates a number of problems, including aliasing.
In particular, computing the intensity of a single pixel requires an integration of a function over the pixel area. This integral is often highly complex and cannot be solved analytically, thus requiring numerical methods for solution, which may include Monte Carlo and quasi-Monte Carlo methods. However, typical numerical methods used in such applications have their own limitations and attendant problems.
Another computational approach used in computer graphics is lattice theory. For example, the accumulation buffer typically used in computer graphics exploits the structure of regular grids. In addition, efficient rasterization techniques have been designed by taking advantage of such grids. Certain sampling techniques employ Fibonacci lattices, which are a type of rank-1 lattice.
It would be desirable to provide methods, systems, devices, and computer software using rank-1 lattices that can be generated rapidly and efficiently, and that are readily adapted to the requirements of image synthesis and other computer graphics applications.
It would also be desirable to provide such methods, systems, devices and software that enable the efficient application of rank-1 lattices to anti-aliasing, rasterization, and other computer graphics functions.
Image synthesis by use of rank-1 lattices is discussed in commonly owned U.S. application Ser. No. 11/474,091 and PCT Application Serial No. PCT/US06/024820, both filed Jun. 23, 2006, and entitled “Image Synthesis by Rank-1 Lattices”each of which is incorporated herein by reference as if set forth in its entirety.
The algorithmic benefits of rank-1 lattices selected by maximized minimum distance (MMD) were discussed in the noted patent applications in the context of image synthesis. Compared to classical tensor product lattices, their geometry allows for a higher sampling efficiency resulting in a better image quality at same storage cost. Therefore, rank-1 lattice images are a potentially advantageous alternative to the traditional square pixel layout.
However, finding the best MMD rank-1 lattice for a given unit square and number of lattice points n can be computationally expensive. In certain cases, the best MMD rank-1 lattice can be determined by a formula. However, in other cases, the best MMD rank-1 lattice can only be found through an exhaustive search.
There is thus a need for systems and techniques for conducting an efficient search for the best MMD rank-1 lattice, or a reasonably close approximation thereof.